Iterative and Multigrid Methods

CS556 :: Fall 2026

Class Time	Monday/Wednesday, 11:00 a.m.–12:15 p.m. [Catalog]
Class Location	1214 Siebel Center for Computer Science
Class URL	go.illinois.edu/cs556
Instructor	Luke Olson

About the Course Lectures Homework On Attendance Mental Health and Wellness

About the Course

Do you have a large, sparse matrix or graph problem that you'd like to solve? Then this course is for you!

The linear system A x = b: the nonzero entries of A form a narrow band along the diagonal, leaving most of the matrix empty, while x and b are dense columns.

The course covers roughly three topics: the fundamentals of numerical linear algebra, iterative methods (such as CG and GMRES), and multilevel methods (for example, geometric and algebraic multigrid).

The course involves homeworks and a final project. There is also a strong participation grade based on your attendance (informal) and ability to keep up with handouts and other tasks. The tentative grade breakdown is:

Homework: 40%
Final project: 50%
Attendance and handouts: 10%

This will be finalized by the first week of class.

The final project will be built over the last half (approximately) of the semester, with several steps, depending on the course size:

prj00: topic selection
prj01: description of the topic, with steps
prj02: goals and workflow
prj03: setup and initial results
prj04: summary of a peer project
prj05: critique of a peer project
prj06: draft slides (1-3 slides, format given in class)
prj07: final slides (due before the first presentation)

The course homeworks and examples in class will be in Python. In particular, we will use the sparse features in SciPy and the solvers in PyAMG.

Lectures

August
08-24 01

About the course, errors and residuals, my first iterative method, sparse matrices

IPYNBmy_first_iterative_method.ipynb IPYNBerror_vs_residual.ipynb IPYNBsparse_matrices.ipynb IPYNBsparse_matvec_basics.ipynb IPYNBsparse_lu.ipynb
08-26 02

Jacobi, Gauss-Seidel, convergence criteria

IPYNBsparse_matrices.ipynb IPYNBsparse_matvec_basics.ipynb IPYNBsparse_cost.ipynb IPYNBrelaxation.ipynb IPYNBrichardson.ipynb
08-31 03

A general projection method

IPYNBrelaxation.ipynb IPYNBrichardson.ipynb
September
09-02 04

One-dimensional projection methods

onedprojection.pyIPYNBonedprojection_demo.ipynb
09-07

Labor Day — no class
09-09 05

Intro to Krylov spaces

cg.pyIPYNBarnoldi_basic.ipynb IPYNBcg_example.ipynb IPYNBkrylov_basic.ipynb
09-14 06

The full orthogonalization method and polynomials

arnoldi.py fom.pyIPYNBarnoldi_example.ipynb IPYNBfom_example.ipynb IPYNBminimum_polynomial.ipynb
09-16 07

GMRES
09-21 08

CG+GMRES convergence

gmres_mgs.pyIPYNBgmres_example.ipynb
09-23 09

Preconditioned Krylov methods

cg.pyIPYNBcg_example.ipynb IPYNBgeikj.ipynb IPYNBilu_preconditioning.ipynb
09-28 10

Relaxation methods

IPYNBmg-01-model-problem.ipynb IPYNBmg-02-relaxation-Jacobi.ipynb IPYNBmg-03-smooth-error.ipynb
09-30 11

Smooth error, coarse-grid correction

IPYNBmg-02-relaxation-Jacobi.ipynb IPYNBmg-03-smooth-error.ipynb IPYNBmg-04-coarse-modes.ipynb
October
10-05 12

Coarse-grid correction and a two-level method

IPYNBmg-05-interpolation.ipynb IPYNBmg-06-multigrid-two-level.ipynb
10-07 13

Multigrid accuracy and cost

IPYNBmg-07-multigrid-two-level-matrix-form.ipynb IPYNBmg-08-multigrid-v-cycle.ipynb
10-12 14

Multigrid in 2D, anisotropy, variable coarsening

IPYNBmg-08-multigrid-v-cycle.ipynb IPYNBmg-09-multigrid-2d.ipynb
10-14 15

Anisotropy, line relaxation, coarse meshes

IPYNBmg-10-multigrid-anisotropy.ipynb IPYNBmg-11-multigrid-2d-line-relaxation.ipynb IPYNBmg-12-AMG-coarse-mesh.ipynb
10-19 16

AMG, by CF splitting

IPYNBmg-12-AMG-coarse-mesh.ipynb IPYNBmg-13-rotated-anisotropy.ipynb IPYNBmg-14-anisotropy-cf-amg.ipynb IPYNBmg-15-CF-AMG-interpolation.ipynb
10-21 17

AMG, by CF splitting (cont.)

IPYNBmg-12-AMG-coarse-mesh.ipynb IPYNBmg-13-rotated-anisotropy.ipynb IPYNBmg-14-anisotropy-cf-amg.ipynb IPYNBmg-15-CF-AMG-interpolation.ipynb
10-26 18

AMG, by smoothed aggregation

IPYNBmg-16-aggregation.ipynb IPYNBmg-17-smoothed-aggregation-1d.ipynb IPYNBmg-18-components-of-smoothed-aggregation.ipynb
10-28 19

Advanced AMG

IPYNBmg-17-smoothed-aggregation-1d.ipynb IPYNBmg-18-components-of-smoothed-aggregation.ipynb
November
11-02 20

Advanced AMG, AMG theory

IPYNBmg-19-advanced-options-anisotropy.ipynb IPYNBmg-20-advanced-options-nonsymmetric-flow.ipynb IPYNBmg-21-advanced-options-systems-elasticity.ipynb
11-04 21

AMG, theory
11-09 22

TBD
11-11 23

Parallel AMG
11-16 24

ILU preconditioning
11-18 25

Domain decomposition
11-30 26

Domain decomposition and convergence
December
12-02 27

Domain decomposition and convergence (cont.)
12-07 28

Nonlinear solvers, project blitz
12-09 29

Nonlinear solvers, project blitz (cont.)

Books

We will be using Saad's book Iterative Methods for Sparse Linear Systems

In addition, there are several other helpful texts (optional):

On Attendance

If you have cold-like symptoms or otherwise do not feel well, please stay home.

Missing class because you are ill will not affect your grade, and I will work with you to cover the material, over Zoom if that helps.

Mental Health and Wellness

Significant stress, mood changes, excessive worry, substance/alcohol misuse or interferences in eating or sleep can have an impact on academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings which are covered through the Student Health Fee. If you or someone you know experiences any of the above mental health concerns, we strongly encourage you to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do for yourself and for those who care about you.

Counseling Center (217) 333-3704
McKinley Health Center (217) 333-2700
988 Suicide & Crisis Lifeline — call or text 988, or chat at 988lifeline.org
Rosecrance Crisis Line (217) 359-4141 (available 24/7, 365 days a year)
If you are in immediate danger, call 911.

Adapted from the statement approved by the University of Illinois Counseling Center.